#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <bitset>
#include <utility>
using namespace std;

#define mm(a, n) memset(a, n, sizeof a)
#define mk(a, b) make_pair(a, b)

const double eps = 1e-6;
const int INF = 0x3f3f3f3f;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<LL, LL> PLL;
typedef pair<int, LL> PIL;

inline void quickread() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}


using namespace std;

const int N = 510, M = N * N;

int n, m, S, T;
int h[N], e[M], w1[M], w2[M], ne[M], idx;
int dist1[N], dist2[N], pre[N];
bool st[N];

void add(int a, int b, int c, int d) {
    e[idx] = b, w1[idx] = c, w2[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;
}

pair<int, string> dijkstra(int w1[], int w2[], int type) {
    mm(dist1, INF);
    mm(dist2, INF);
    mm(st, 0);
    dist1[S] = dist2[S] = 0;

    for (int i = 0; i < n; i ++ ) {
        int t = -1;
        for (int j = 0; j < n; j ++ )
            if (!st[j] && (t == -1 || dist1[t] > dist1[j]))
                t = j;

        st[t] = true;
        
        for (int u = h[t]; ~u; u = ne[u]) {
            int j = e[u];
            int cost;
            if (type == 0) cost = w2[u];
            else cost = 1;

            if (dist1[j] > dist1[t] + w1[u]) {
                dist1[j] = dist1[t] + w1[u];
                dist2[j] = dist2[t] + cost;
                pre[j] = t;
            }
            else if (dist1[j] == dist1[t] + w1[u]) {
                if (dist2[j] > dist2[t] + cost) {
                    dist2[j] = dist2[t] + cost;
                    pre[j] = t;
                }
            }
        }
    }

    vector<int> path;
    for (int i = T; i != S; i = pre[i]) path.push_back(i);

    pair<int, string> res;
    res.first = dist1[T];
    res.second = to_string(S);
    for (int i = path.size() - 1; i >= 0; i -- )
        res.second += " -> " + to_string(path[i]);
    return res;
}


inline void solution() {
    cin >> n >> m;
    mm(h, -1);
    while (m -- ) {
        int a, b, t, c, d;
        cin >> a >> b >> t >> c >> d;
        add(a, b, c, d);
        if (!t) add(b, a, c, d);
    }

    cin >> S >> T;

    auto A = dijkstra(w1, w2, 0); // 第一个关键字是最短路，第二个关键字是时间
    auto B = dijkstra(w2, w1, 1); // 第一个关键字是时间，第二个关键字是节点数

    if (A.second != B.second) {
        printf("Distance = %d: %s\n", A.first, A.second.c_str());
        printf("Time = %d: %s\n", B.first, B.second.c_str());
    }
    else
        printf("Distance = %d; Time = %d: %s\n", A.first, B.first, A.second.c_str());
}

int main() {
    freopen("input.txt", "r", stdin);
    quickread();
    solution();
    return 0;
}